여 그래프

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 성질
- 3.1. 자기 여 그래프
4. 응용
5. 관련 그래프
참조

1. 개요

여 그래프는 주어진 그래프 G와 정점 집합은 같지만, G에 간선이 없는 정점 쌍을 간선으로 가지는 그래프이다. 여 그래프의 여 그래프는 원래 그래프와 같으며, 원래 그래프의 독립 집합은 여 그래프의 클리크와 같다. 자기 여 그래프는 자신의 여 그래프와 동형인 그래프를 의미하며, 4개의 정점을 가진 경로 그래프, 5개의 정점을 가진 순환 그래프가 그 예시이다. 여 그래프는 램지 이론 및 NP-완전 문제 증명에 활용되며, 알고리즘 분석에서 그래프와 그 여 그래프 간의 구분은 중요하다.

더 읽어볼만한 페이지

그래프 이론 - 다이어그램
다이어그램은 2차원 기하학적 기호를 사용하여 정보를 시각적으로 표현하는 기술로, 과학, 공학, IT, 비즈니스 등 다양한 분야에서 활용되며 정보를 간략하게 나타내고 시각적 사고를 돕는다.
그래프 이론 - 쾨니히스베르크의 다리 문제
쾨니히스베르크의 다리 문제는 프레겔 강에 놓인 7개의 다리를 한 번씩만 건너 출발점으로 되돌아올 수 있는지 묻는 문제로, 오일러에 의해 그래프 이론적으로 분석되어 해결되었으며 그래프 이론의 탄생에 기여했다.

여 그래프
그래프 정보
종류	그래프 이론
정의	그래프의 꼭짓점 집합은 동일하게 유지하고, 간선 집합은 원래 그래프에 없는 간선들로 구성된 그래프
다른 이름	여 그래프
관련 개념
자기 보완 그래프	자기 자신과 補그래프가 동형인 그래프
완전 그래프	모든 꼭짓점 쌍 사이에 간선이 있는 그래프
독립 집합	그래프 내에서 서로 인접하지 않은 꼭짓점들의 집합
클리크	그래프 내에서 모든 꼭짓점들이 서로 인접한 꼭짓점들의 집합
성질
독립 집합과 클리크 관계	그래프의 독립 집합은 補그래프의 클리크이며, 그 반대도 성립한다.
완전 그래프 분할	n개의 꼭짓점을 가진 그래프와 補그래프 중 적어도 하나는 n개의 꼭짓점을 가진 완전 그래프로 분할 가능하다.
자기 보완 그래프 존재 조건	n개의 꼭짓점을 가진 자기 보완 그래프는 n ≡ 0 또는 1 (mod 4)일 때만 존재한다.

2. 정의

그래프 $G$ 의 여 그래프 $\bar G$ 는 다음과 같이 정의된다.^[2]

$V(G)=V(\bar G)$
$uv\in E(\bar G)\iff uv\not\in E(G)$

다른 표현으로, 를 단순 그래프라고 하고, 가 의 모든 2원소 부분 집합으로 구성된다고 하자. 그러면 는 의 보수 그래프이며, 여기서 는 에서 의 상대 보수(차집합)이다.

유향 그래프의 경우에도, 보수 그래프는 동일한 정점 집합에서 위와 유사한 방식으로 정의할 수 있다. 다만, 집합 대신 의 모든 2원소 순서쌍 집합을 사용한다. 그래프의 인접 행렬 ''A''의 관점에서, 만약 ''Q''가 동일한 수의 정점을 가진 완전 그래프의 인접 행렬이라면 (즉, 대각선 요소를 제외한 모든 항목이 1이고 대각선 요소는 0), ''A''의 보수 그래프의 인접 행렬은 ''Q-A''이다.

여 그래프는 멀티 그래프에 대해서는 정의되지 않는다.

3. 성질

여 그래프의 여 그래프는 원래 그래프와 같다.

: $G\cong\bar{\bar G}$

원래 그래프의 독립집합은 여 그래프의 클리크와 같고, 그 반대도 성립한다.

3. 1. 자기 여 그래프

자기 여 그래프는 자신의 여 그래프와 동형인 그래프를 의미한다.^[1] 4개의 정점을 가진 경로 그래프와 5개의 정점을 가진 순환 그래프가 자기 여 그래프의 예시이다.^[1]

n

개의 꼭짓점을 갖는 자기 여 그래프의 수는

n=1,2,\dots

에 대해 1, 0, 0, 1, 2, 0, 0, 10, 36, 0, 0, 720, … 순서로 나타난다. 유한 자기 여 그래프의 꼭짓점의 수는

n\equiv0,1\pmod4

를 만족해야 하는데, 이는 가능한 변의 수

n(n-1)/2

가 짝수여야 하기 때문이다.

4. 응용

여 그래프는 램지 이론 등 그래프 이론의 여러 분야에서 활용된다.^[3] NP-완전 문제 증명에도 활용된다.

그래프에 대한 알고리즘 분석에서 그래프와 그 여 그래프 간의 구분은 중요하다. 희소 그래프(정점 쌍의 수에 비해 간선 수가 적은 그래프)는 일반적으로 희소 여 그래프를 갖지 않으므로, 주어진 그래프의 간선 수에 비례하는 시간이 걸리는 알고리즘은 여 그래프의 명시적 표현에서 동일한 알고리즘을 실행할 경우 훨씬 더 많은 시간이 걸릴 수 있기 때문이다.^[8] 따라서 연구자들은 여 그래프를 명시적으로 구성할 필요가 없는 암시적 그래프 표현을 사용하여 입력 그래프의 여 그래프에 대해 표준 그래프 계산을 수행하는 알고리즘을 연구해 왔다. 특히, 여 그래프의 크기가 훨씬 클 수 있음에도 불구하고 주어진 그래프의 크기에 선형적인 시간 내에 여 그래프에 대해 깊이 우선 탐색 또는 너비 우선 탐색을 시뮬레이션하는 것이 가능하다.^[8] 이러한 시뮬레이션을 사용하여 여 그래프의 연결성에 관한 다른 속성을 계산하는 것도 가능하다.^[8]^[9]

5. 관련 그래프

완전 그래프는 모든 정점 쌍이 변으로 연결된 그래프이다. 완전 그래프의 보완 그래프도 완전 그래프라는 사실은 러슬로 러바츠의 완전 그래프 정리이다.^[4] 코그래프는 단일 정점에서 시작하여 분리 집합 및 보완 연산을 통해 구성할 수 있는 그래프이다. 모든 코그래프의 보완 그래프는 다른 코그래프이다.^[5] 분할 그래프는 정점을 클릭과 독립 집합으로 분할할 수 있는 그래프이며, 동일한 분할은 보완 그래프에서 독립 집합과 클릭을 제공한다.^[6] 임계 그래프는 독립적인 정점(이웃이 없는 정점) 또는 전체 정점 (이전에 추가된 모든 정점에 인접한 정점)을 반복적으로 추가하여 형성된 그래프로, 이 두 연산은 상호 보완적이며 자기 보완적인 그래프 종류를 생성한다.^[7]

참조

_[1] 서적 Graph Theory with Applications https://archive.org/[...] North-Holland
_[2] 서적 Graph Theory http://diestel-graph[...] Springer Science+Business Media
_[3] 간행물 Surveys in combinatorics 2005 Cambridge Univ. Press
_[4] 논문 Normal hypergraphs and the perfect graph conjecture
_[5] 논문 Complement reducible graphs
_[6] 서적 Algorithmic Graph Theory and Perfect Graphs Academic Press
_[7] 논문 Rank-tolerance graph classes
_[8] 논문 Linear time algorithms for graph search and connectivity determination on complement graphs
_[9] 논문 Simple and efficient graph compression schemes for dense and complement graphs

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com